package hash;

import java.util.HashMap;

/**
 * 可以随机获取添加的元素
 *
 * @author Liaorun
 */
public class RandomPool {
    public static class Pool<K> {
        private HashMap<K, Integer> keyIndexMap;
        private HashMap<Integer, K> indexKeyMap;

        private int size;

        public Pool() {
            this.keyIndexMap = keyIndexMap;
            this.indexKeyMap = indexKeyMap;
            this.size = 0;
        }


        public void insert(K key) {
            if (!this.keyIndexMap.containsKey(key)) {
                // 没有添加过该元素，在最后一个位置添加该元素
                this.keyIndexMap.put(key, this.size);
                this.indexKeyMap.put(this.size, key);
                // 元素数量++
                size++;
            }
        }

        public void delete(K key) {
            if (this.keyIndexMap.containsKey(key)) {
                // 需要删除元素的下标
                Integer deleteIndex = this.keyIndexMap.get(key);
                // 最后一个下标
                int lastIndex = --this.size;
                // 获取最后一个元素
                K lastKey = this.indexKeyMap.get(lastIndex);
                // 将最后一个元素放到删除元素的位置，此时有两个元素绑定deleteIndex
                this.keyIndexMap.put(lastKey, deleteIndex);
                // 将删除元素的指针指向最后一个元素
                this.indexKeyMap.put(deleteIndex, lastKey);

                // 删除需要删除的元素
                this.keyIndexMap.remove(key);
                this.indexKeyMap.remove(lastIndex);
            }
        }

        public K getRandom() {
            if (this.size == 0) {
                return null;
            }

            // 0 ~ size - 1
            int random = (int) (Math.random() * this.size);

            return this.indexKeyMap.get(random);
        }
    }
}
